﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 原题连接：https://leetcode.cn/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
/*
题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]
*/

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

//  开始解题：
bool dfs(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q, struct TreeNode** ansRoot) {
    if (NULL == root) {
        return false;
    }
    bool lson = dfs(root->left, p, q, ansRoot);
    bool rson = dfs(root->right, p, q, ansRoot);
    if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
        *ansRoot = root;
    }
    return lson || rson || (root->val == p->val || root->val == q->val);
}


struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    struct TreeNode* ansRoot;
    dfs(root, p, q, &ansRoot);
    return ansRoot;

}